#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

const int kMaxN = 1e5 + 10;

pair<int, int> p[kMaxN];

bool Check(int n, int d, int w) {
  deque<pair<int, int>> max_deq, min_deq;
  for (int i = 0; i < n; i++) {
    for (; !max_deq.empty() && max_deq.back().second <= p[i].second; max_deq.pop_back());
    max_deq.push_back(p[i]);
    for (; !min_deq.empty() && min_deq.back().second >= p[i].second; min_deq.pop_back());
    min_deq.push_back(p[i]);
    for (; max_deq.front().first + w < p[i].first; max_deq.pop_front());
    for (; min_deq.front().first + w < p[i].first; min_deq.pop_front());
    if (max_deq.front().second - min_deq.front().second >= d) {
      return true;
    }
  }
  return false;
}

int Solve(int n, int d, int maxw) {
  int l = 0, r = maxw;

  sort(p, p + n);
  while (l < r) {
    int m = (l + r) >> 1;
    if (Check(n, d, m)) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  return l;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, d;
  int miny = 1e6, maxy = 0;
  int minx = 1e6, maxx = 0;

  cin >> n >> d;
  for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
    minx = min(minx, p[i].first);
    maxx = max(maxx, p[i].first);
    miny = min(miny, p[i].second);
    maxy = max(maxy, p[i].second);
  }
  if (maxy - miny < d) {
    cout << "-1\n";
  } else {
    cout << Solve(n, d, maxx - minx) << "\n";
  }
  return 0;
}